class Node():
    """创建一个结点类"""

    def __init__(self, data):
        self.data = data
        self.pre = None
        self.next = None

class DoubleLink():
    """创建一个创建双向链表的类"""
    def __init__(self):
        self.head = None

    def is_empty(self):
        """判断双向链表是否为空链表"""
        if self.head == None:
            return True
        else:
            return False

    def insertToHead(self,value):
        node = Node(value)
        if self.is_empty():
            self.head = node
        else:
            # 头结点向前指向新节点
            self.head.pre = node
            #新节点向后指向头结点
            node.next = self.head
            #将头节点的称号给新节点
            self.head = node

    def insertToTail(self,value):
        node = Node(value)
        if self.is_empty():
            self.head = node
            node.next = None
            node.pre = None
            return
        else:
            cur = self.head
            # 指针移动到尾部
            while cur.next is not None:
                cur = cur.next
            # 尾结点的后继指针指向新结点
            cur.next = node
            # 新结点的前驱指针指向尾结点
            node.pre = cur

    def length(self):
        """获取双向链表的长度"""
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def traversal(self):
        """遍历双向链表"""
        cur = self.head
        if self.is_empty():
            print("链表为空！")
            return
        else:
            while cur is not None:
                print(cur.data,end="")
                cur = cur.next
            print()

    def insert_node(self,index,value):
        """在指定位置添加节点"""
        if index < 0 or index > self.length():
            print("结点位置错误！")
            return False
        elif index == 0:
            self.insertToHead(value)
        elif index == self.length():
            self.insertToTail(value)
        else:
            node = Node(value)
            cur = self.head
            pres = None
            count = 0
            #移动指定位置
            while count < index:
                pres = cur
                cur = cur.next
                count += 1
            pres.next = node
            node.pre = pres
            node.next = cur
            cur.pre = node


    def node_is_exist(self, data):
        """查找指定结点是否存在"""
        cur = self.head
        while cur is not None:
            if cur.data == data:
                return True
            else:
                cur = cur.next
        return False

if __name__ == '__main__':
    dl = DoubleLink()
    if dl.is_empty():
        print("此双向链表为空!")
    else:
        print("此双向链表不为空!")

    print("使用头插法的结果：",end="")
    for i in range(1, 6):
        dl.insertToHead(i)
    dl.traversal()

    # print("使用尾插法的结果：", end="")
    # for i in range(6,10):
    #     dl.insertToTail()
    # dl.traversal()
    i = 6
    while i <= 10:
        dl.insertToTail(i)
        i += 1
    print("尾插法的结果：",end="")
    dl.traversal()
    print("获取链表长度：",dl.length())
    dl.insert_node(3, 520)
    print("指定位置插入：", end="")
    dl.traversal()